package com.zjsru.plan2025.oneday;

/**
 * 2873. 有序三元组中的最大值 I
 * @Author: cookLee
 * @Date: 2025-04-05
 */
public class MaximumTripletValue {

    /**
     * 主
     * \
     * 请你从所有满足 i < j < k 的下标三元组 (i, j, k) 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 0 。
     * 下标三元组 (i, j, k) 的值等于 (nums[i] - nums[j]) * nums[k] 。
     * \
     * 输入：nums = [12,6,1,2,7]
     * 输出：77
     * 解释：下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。
     * 可以证明不存在值大于 77 的有序下标三元组。
     * \
     * 输入：nums = [1,10,3,4,19]
     * 输出：133
     * 解释：下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。
     * 可以证明不存在值大于 133 的有序下标三元组。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MaximumTripletValue maximumTripletValue = new MaximumTripletValue();
        int[] nums = new int[]{12, 6, 1, 2, 7};
        System.out.println(maximumTripletValue.maximumTripletValue2(nums));
    }

    /**
     * 暴力破解
     *
     * @param nums nums
     * @return long
     */
    public long maximumTripletValue(int[] nums) {
        long ans = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                for (int k = j + 1; k < len; k++) {
                    ans = Math.max(ans, (long) (nums[i] - nums[j]) * nums[k]);
                }
            }
        }
        return ans;
    }

    /**
     * 枚举两边乘积
     *
     * @param nums nums
     * @return long
     */
    public long maximumTripletValue2(int[] nums) {
        int len = nums.length;
        int[] sufMax = new int[len + 1];
        for (int i = len - 1; i > 0; i--) {
            sufMax[i] = Math.max(sufMax[i + 1], nums[i]);
        }
        long ans = 0;
        int preMax = nums[0];
        for (int i = 1; i < len - 1; i++) {
            ans = Math.max(ans, (long) (preMax - nums[i]) * sufMax[i + 1]);
            preMax = Math.max(preMax, nums[i]);
        }
        return ans;
    }

}
